package lcr;

import java.util.Arrays;

public class Test0112 {
}

class Solution_0112_1 {
    int length1=0;
    int length2=0;
    int[][] t =new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    public int longestIncreasingPath(int[][] matrix) {
        this.length1 = matrix.length;
        this.length2 = matrix[0].length;

        int[][] record=new int[length1][length2];
        for (int i = 0; i < length1; i++) Arrays.fill(record[i],-1);

        int ans=0;
        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                if (record[i][j]<0) dfs(matrix,record,i,j);
                ans=Math.max(record[i][j],ans);
            }
        }

        return ans;
    }

    public int dfs(int[][] matrix,int[][] record,int rowIndex,int columnIndex){
        int now = matrix[rowIndex][columnIndex];

        int result = record[rowIndex][columnIndex];
        if (result >0) return result;
        else result=1;

        int add=0;
        for (int[] ints : t) {
            int rowIndex1=rowIndex+ints[0];
            int columnIndex1=columnIndex+ints[1];

            if (rowIndex1>=0
                    &&columnIndex1>=0
                    &&rowIndex1<length1
                    &&columnIndex1<length2
                    &&matrix[rowIndex1][columnIndex1]>now){
                add=Math.max(dfs(matrix,record,rowIndex1,columnIndex1),add);
            }
        }
        result+=add;

        record[rowIndex][columnIndex]=result;
        return result;
    }
}
